The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(2^n, INF).

(0) Obligation:

Runtime Complexity TRS:
The TRS R consists of the following rules:

0(#) → #
+(x, #) → x
+(#, x) → x
+(0(x), 0(y)) → 0(+(x, y))
+(0(x), 1(y)) → 1(+(x, y))
+(1(x), 0(y)) → 1(+(x, y))
+(1(x), 1(y)) → 0(+(+(x, y), 1(#)))
+(+(x, y), z) → +(x, +(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +(log'(x), 1(#)), #)
*(#, x) → #
*(0(x), y) → 0(*(x, y))
*(1(x), y) → +(0(*(x, y)), y)
*(*(x, y), z) → *(x, *(y, z))
*(x, +(y, z)) → +(*(x, y), *(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +(x, sum(l))
sum(app(l1, l2)) → +(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *(x, prod(l))
prod(app(l1, l2)) → *(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Rewrite Strategy: FULL

(1) DecreasingLoopProof (EQUIVALENT transformation)

The following loop(s) give(s) rise to the lower bound Ω(2ⁿ):
The rewrite sequence
prod(cons(1(x322657_4), l)) →⁺ +(0(*(x322657_4, prod(l))), prod(l))
gives rise to a decreasing loop by considering the right hand sides subterm at position [0,0,1].
The pumping substitution is [l / cons(1(x322657_4), l)].
The result substitution is [ ].

The rewrite sequence
prod(cons(1(x322657_4), l)) →⁺ +(0(*(x322657_4, prod(l))), prod(l))
gives rise to a decreasing loop by considering the right hand sides subterm at position [1].
The pumping substitution is [l / cons(1(x322657_4), l)].
The result substitution is [ ].

(2) BOUNDS(2^n, INF)

(3) RenamingProof (EQUIVALENT transformation)

Renamed function symbols to avoid clashes with predefined symbol.

(4) Obligation:

Runtime Complexity Relative TRS:
The TRS R consists of the following rules:

0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

S is empty.
Rewrite Strategy: FULL

(5) TypeInferenceProof (BOTH BOUNDS(ID, ID) transformation)

Infered types.

(6) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

(7) OrderProof (LOWER BOUND(ID) transformation)

Heuristically decided to analyse the following defined symbols:
+', -, eq, ge, log', *', app, sum, prod, mem, inter

They will be analysed ascendingly in the following order:
+' < log'
+' < *'
+' < sum
eq < mem
ge < log'
*' < prod
app < inter
mem < inter

(8) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

The following defined symbols remain to be analysed:
+', -, eq, ge, log', *', app, sum, prod, mem, inter

They will be analysed ascendingly in the following order:
+' < log'
+' < *'
+' < sum
eq < mem
ge < log'
*' < prod
app < inter
mem < inter

(9) NoRewriteLemmaProof (LOWER BOUND(ID) transformation)

Could not prove a rewrite lemma for the defined symbol +'.

(10) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

The following defined symbols remain to be analysed:
-, eq, ge, log', *', app, sum, prod, mem, inter

They will be analysed ascendingly in the following order:
eq < mem
ge < log'
*' < prod
app < inter
mem < inter

(11) RewriteLemmaProof (LOWER BOUND(ID) transformation)

Proved the following rewrite lemma:
-(gen_#:1:true:false3_4(n108770_4), gen_#:1:true:false3_4(n108770_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n108770₄)

Induction Base:
-(gen_#:1:true:false3_4(0), gen_#:1:true:false3_4(0)) →_R^Ω(1)
#

Induction Step:
-(gen_#:1:true:false3_4(+(n108770_4, 1)), gen_#:1:true:false3_4(+(n108770_4, 1))) →_R^Ω(1)
0(-(gen_#:1:true:false3_4(n108770_4), gen_#:1:true:false3_4(n108770_4))) →_IH
0(gen_#:1:true:false3_4(0)) →_R^Ω(1)
#

We have rt ∈ Ω(n¹) and sz ∈ O(n). Thus, we have irc_R ∈ Ω(n).

(12) Complex Obligation (BEST)

(13) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
-(gen_#:1:true:false3_4(n108770_4), gen_#:1:true:false3_4(n108770_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n108770₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

The following defined symbols remain to be analysed:
eq, ge, log', *', app, sum, prod, mem, inter

They will be analysed ascendingly in the following order:
eq < mem
ge < log'
*' < prod
app < inter
mem < inter

(14) RewriteLemmaProof (LOWER BOUND(ID) transformation)

Proved the following rewrite lemma:
eq(gen_#:1:true:false3_4(n111029_4), gen_#:1:true:false3_4(n111029_4)) → true, rt ∈ Ω(1 + n111029₄)

Induction Base:
eq(gen_#:1:true:false3_4(0), gen_#:1:true:false3_4(0)) →_R^Ω(1)
true

Induction Step:
eq(gen_#:1:true:false3_4(+(n111029_4, 1)), gen_#:1:true:false3_4(+(n111029_4, 1))) →_R^Ω(1)
eq(gen_#:1:true:false3_4(n111029_4), gen_#:1:true:false3_4(n111029_4)) →_IH
true

We have rt ∈ Ω(n¹) and sz ∈ O(n). Thus, we have irc_R ∈ Ω(n).

(15) Complex Obligation (BEST)

(16) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
-(gen_#:1:true:false3_4(n108770_4), gen_#:1:true:false3_4(n108770_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n108770₄)
eq(gen_#:1:true:false3_4(n111029_4), gen_#:1:true:false3_4(n111029_4)) → true, rt ∈ Ω(1 + n111029₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

The following defined symbols remain to be analysed:
ge, log', *', app, sum, prod, mem, inter

They will be analysed ascendingly in the following order:
ge < log'
*' < prod
app < inter
mem < inter

(17) RewriteLemmaProof (LOWER BOUND(ID) transformation)

Proved the following rewrite lemma:
ge(gen_#:1:true:false3_4(n143674_4), gen_#:1:true:false3_4(n143674_4)) → true, rt ∈ Ω(1 + n143674₄)

Induction Base:
ge(gen_#:1:true:false3_4(0), gen_#:1:true:false3_4(0)) →_R^Ω(1)
true

Induction Step:
ge(gen_#:1:true:false3_4(+(n143674_4, 1)), gen_#:1:true:false3_4(+(n143674_4, 1))) →_R^Ω(1)
ge(gen_#:1:true:false3_4(n143674_4), gen_#:1:true:false3_4(n143674_4)) →_IH
true

We have rt ∈ Ω(n¹) and sz ∈ O(n). Thus, we have irc_R ∈ Ω(n).

(18) Complex Obligation (BEST)

(19) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
-(gen_#:1:true:false3_4(n108770_4), gen_#:1:true:false3_4(n108770_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n108770₄)
eq(gen_#:1:true:false3_4(n111029_4), gen_#:1:true:false3_4(n111029_4)) → true, rt ∈ Ω(1 + n111029₄)
ge(gen_#:1:true:false3_4(n143674_4), gen_#:1:true:false3_4(n143674_4)) → true, rt ∈ Ω(1 + n143674₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

The following defined symbols remain to be analysed:
log', *', app, sum, prod, mem, inter

They will be analysed ascendingly in the following order:
*' < prod
app < inter
mem < inter

(20) NoRewriteLemmaProof (LOWER BOUND(ID) transformation)

Could not prove a rewrite lemma for the defined symbol log'.

(21) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
-(gen_#:1:true:false3_4(n108770_4), gen_#:1:true:false3_4(n108770_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n108770₄)
eq(gen_#:1:true:false3_4(n111029_4), gen_#:1:true:false3_4(n111029_4)) → true, rt ∈ Ω(1 + n111029₄)
ge(gen_#:1:true:false3_4(n143674_4), gen_#:1:true:false3_4(n143674_4)) → true, rt ∈ Ω(1 + n143674₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

The following defined symbols remain to be analysed:
*', app, sum, prod, mem, inter

They will be analysed ascendingly in the following order:
*' < prod
app < inter
mem < inter

(22) RewriteLemmaProof (LOWER BOUND(ID) transformation)

Proved the following rewrite lemma:
*'(gen_#:1:true:false3_4(n242826_4), gen_#:1:true:false3_4(0)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n242826₄)

Induction Base:
*'(gen_#:1:true:false3_4(0), gen_#:1:true:false3_4(0)) →_R^Ω(1)
#

Induction Step:
*'(gen_#:1:true:false3_4(+(n242826_4, 1)), gen_#:1:true:false3_4(0)) →_R^Ω(1)
+'(0(*'(gen_#:1:true:false3_4(n242826_4), gen_#:1:true:false3_4(0))), gen_#:1:true:false3_4(0)) →_IH
+'(0(gen_#:1:true:false3_4(0)), gen_#:1:true:false3_4(0)) →_R^Ω(1)
+'(#, gen_#:1:true:false3_4(0)) →_R^Ω(1)
#

We have rt ∈ Ω(n¹) and sz ∈ O(n). Thus, we have irc_R ∈ Ω(n).

(23) Complex Obligation (BEST)

(24) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
-(gen_#:1:true:false3_4(n108770_4), gen_#:1:true:false3_4(n108770_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n108770₄)
eq(gen_#:1:true:false3_4(n111029_4), gen_#:1:true:false3_4(n111029_4)) → true, rt ∈ Ω(1 + n111029₄)
ge(gen_#:1:true:false3_4(n143674_4), gen_#:1:true:false3_4(n143674_4)) → true, rt ∈ Ω(1 + n143674₄)
*'(gen_#:1:true:false3_4(n242826_4), gen_#:1:true:false3_4(0)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n242826₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

The following defined symbols remain to be analysed:
app, sum, prod, mem, inter

They will be analysed ascendingly in the following order:
app < inter
mem < inter

(25) RewriteLemmaProof (LOWER BOUND(ID) transformation)

Proved the following rewrite lemma:
app(gen_nil:cons4_4(n257263_4), gen_nil:cons4_4(b)) → gen_nil:cons4_4(+(n257263_4, b)), rt ∈ Ω(1 + n257263₄)

Induction Base:
app(gen_nil:cons4_4(0), gen_nil:cons4_4(b)) →_R^Ω(1)
gen_nil:cons4_4(b)

Induction Step:
app(gen_nil:cons4_4(+(n257263_4, 1)), gen_nil:cons4_4(b)) →_R^Ω(1)
cons(#, app(gen_nil:cons4_4(n257263_4), gen_nil:cons4_4(b))) →_IH
cons(#, gen_nil:cons4_4(+(b, c257264_4)))

We have rt ∈ Ω(n¹) and sz ∈ O(n). Thus, we have irc_R ∈ Ω(n).

(26) Complex Obligation (BEST)

(27) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
-(gen_#:1:true:false3_4(n108770_4), gen_#:1:true:false3_4(n108770_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n108770₄)
eq(gen_#:1:true:false3_4(n111029_4), gen_#:1:true:false3_4(n111029_4)) → true, rt ∈ Ω(1 + n111029₄)
ge(gen_#:1:true:false3_4(n143674_4), gen_#:1:true:false3_4(n143674_4)) → true, rt ∈ Ω(1 + n143674₄)
*'(gen_#:1:true:false3_4(n242826_4), gen_#:1:true:false3_4(0)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n242826₄)
app(gen_nil:cons4_4(n257263_4), gen_nil:cons4_4(b)) → gen_nil:cons4_4(+(n257263_4, b)), rt ∈ Ω(1 + n257263₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

The following defined symbols remain to be analysed:
sum, prod, mem, inter

They will be analysed ascendingly in the following order:
mem < inter

(28) RewriteLemmaProof (LOWER BOUND(ID) transformation)

Proved the following rewrite lemma:
sum(gen_nil:cons4_4(n258980_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n258980₄)

Induction Base:
sum(gen_nil:cons4_4(0)) →_R^Ω(1)
0(#) →_R^Ω(1)
#

Induction Step:
sum(gen_nil:cons4_4(+(n258980_4, 1))) →_R^Ω(1)
+'(#, sum(gen_nil:cons4_4(n258980_4))) →_IH
+'(#, gen_#:1:true:false3_4(0)) →_R^Ω(1)
#

We have rt ∈ Ω(n¹) and sz ∈ O(n). Thus, we have irc_R ∈ Ω(n).

(29) Complex Obligation (BEST)

(30) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
-(gen_#:1:true:false3_4(n108770_4), gen_#:1:true:false3_4(n108770_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n108770₄)
eq(gen_#:1:true:false3_4(n111029_4), gen_#:1:true:false3_4(n111029_4)) → true, rt ∈ Ω(1 + n111029₄)
ge(gen_#:1:true:false3_4(n143674_4), gen_#:1:true:false3_4(n143674_4)) → true, rt ∈ Ω(1 + n143674₄)
*'(gen_#:1:true:false3_4(n242826_4), gen_#:1:true:false3_4(0)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n242826₄)
app(gen_nil:cons4_4(n257263_4), gen_nil:cons4_4(b)) → gen_nil:cons4_4(+(n257263_4, b)), rt ∈ Ω(1 + n257263₄)
sum(gen_nil:cons4_4(n258980_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n258980₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

The following defined symbols remain to be analysed:
prod, mem, inter

They will be analysed ascendingly in the following order:
mem < inter

(31) NoRewriteLemmaProof (LOWER BOUND(ID) transformation)

Could not prove a rewrite lemma for the defined symbol prod.

(32) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
-(gen_#:1:true:false3_4(n108770_4), gen_#:1:true:false3_4(n108770_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n108770₄)
eq(gen_#:1:true:false3_4(n111029_4), gen_#:1:true:false3_4(n111029_4)) → true, rt ∈ Ω(1 + n111029₄)
ge(gen_#:1:true:false3_4(n143674_4), gen_#:1:true:false3_4(n143674_4)) → true, rt ∈ Ω(1 + n143674₄)
*'(gen_#:1:true:false3_4(n242826_4), gen_#:1:true:false3_4(0)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n242826₄)
app(gen_nil:cons4_4(n257263_4), gen_nil:cons4_4(b)) → gen_nil:cons4_4(+(n257263_4, b)), rt ∈ Ω(1 + n257263₄)
sum(gen_nil:cons4_4(n258980_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n258980₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

The following defined symbols remain to be analysed:
mem, inter

They will be analysed ascendingly in the following order:
mem < inter

(33) NoRewriteLemmaProof (LOWER BOUND(ID) transformation)

Could not prove a rewrite lemma for the defined symbol mem.

(34) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
-(gen_#:1:true:false3_4(n108770_4), gen_#:1:true:false3_4(n108770_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n108770₄)
eq(gen_#:1:true:false3_4(n111029_4), gen_#:1:true:false3_4(n111029_4)) → true, rt ∈ Ω(1 + n111029₄)
ge(gen_#:1:true:false3_4(n143674_4), gen_#:1:true:false3_4(n143674_4)) → true, rt ∈ Ω(1 + n143674₄)
*'(gen_#:1:true:false3_4(n242826_4), gen_#:1:true:false3_4(0)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n242826₄)
app(gen_nil:cons4_4(n257263_4), gen_nil:cons4_4(b)) → gen_nil:cons4_4(+(n257263_4, b)), rt ∈ Ω(1 + n257263₄)
sum(gen_nil:cons4_4(n258980_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n258980₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

The following defined symbols remain to be analysed:
inter

(35) NoRewriteLemmaProof (LOWER BOUND(ID) transformation)

Could not prove a rewrite lemma for the defined symbol inter.

(36) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
-(gen_#:1:true:false3_4(n108770_4), gen_#:1:true:false3_4(n108770_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n108770₄)
eq(gen_#:1:true:false3_4(n111029_4), gen_#:1:true:false3_4(n111029_4)) → true, rt ∈ Ω(1 + n111029₄)
ge(gen_#:1:true:false3_4(n143674_4), gen_#:1:true:false3_4(n143674_4)) → true, rt ∈ Ω(1 + n143674₄)
*'(gen_#:1:true:false3_4(n242826_4), gen_#:1:true:false3_4(0)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n242826₄)
app(gen_nil:cons4_4(n257263_4), gen_nil:cons4_4(b)) → gen_nil:cons4_4(+(n257263_4, b)), rt ∈ Ω(1 + n257263₄)
sum(gen_nil:cons4_4(n258980_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n258980₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

No more defined symbols left to analyse.

(37) LowerBoundsProof (EQUIVALENT transformation)

The lowerbound Ω(n¹) was proven with the following lemma:
-(gen_#:1:true:false3_4(n108770_4), gen_#:1:true:false3_4(n108770_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n108770₄)

(38) BOUNDS(n^1, INF)

(39) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
-(gen_#:1:true:false3_4(n108770_4), gen_#:1:true:false3_4(n108770_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n108770₄)
eq(gen_#:1:true:false3_4(n111029_4), gen_#:1:true:false3_4(n111029_4)) → true, rt ∈ Ω(1 + n111029₄)
ge(gen_#:1:true:false3_4(n143674_4), gen_#:1:true:false3_4(n143674_4)) → true, rt ∈ Ω(1 + n143674₄)
*'(gen_#:1:true:false3_4(n242826_4), gen_#:1:true:false3_4(0)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n242826₄)
app(gen_nil:cons4_4(n257263_4), gen_nil:cons4_4(b)) → gen_nil:cons4_4(+(n257263_4, b)), rt ∈ Ω(1 + n257263₄)
sum(gen_nil:cons4_4(n258980_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n258980₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

No more defined symbols left to analyse.

(40) LowerBoundsProof (EQUIVALENT transformation)

The lowerbound Ω(n¹) was proven with the following lemma:
-(gen_#:1:true:false3_4(n108770_4), gen_#:1:true:false3_4(n108770_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n108770₄)

(41) BOUNDS(n^1, INF)

(42) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
-(gen_#:1:true:false3_4(n108770_4), gen_#:1:true:false3_4(n108770_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n108770₄)
eq(gen_#:1:true:false3_4(n111029_4), gen_#:1:true:false3_4(n111029_4)) → true, rt ∈ Ω(1 + n111029₄)
ge(gen_#:1:true:false3_4(n143674_4), gen_#:1:true:false3_4(n143674_4)) → true, rt ∈ Ω(1 + n143674₄)
*'(gen_#:1:true:false3_4(n242826_4), gen_#:1:true:false3_4(0)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n242826₄)
app(gen_nil:cons4_4(n257263_4), gen_nil:cons4_4(b)) → gen_nil:cons4_4(+(n257263_4, b)), rt ∈ Ω(1 + n257263₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

No more defined symbols left to analyse.

(43) LowerBoundsProof (EQUIVALENT transformation)

The lowerbound Ω(n¹) was proven with the following lemma:
-(gen_#:1:true:false3_4(n108770_4), gen_#:1:true:false3_4(n108770_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n108770₄)

(44) BOUNDS(n^1, INF)

(45) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
-(gen_#:1:true:false3_4(n108770_4), gen_#:1:true:false3_4(n108770_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n108770₄)
eq(gen_#:1:true:false3_4(n111029_4), gen_#:1:true:false3_4(n111029_4)) → true, rt ∈ Ω(1 + n111029₄)
ge(gen_#:1:true:false3_4(n143674_4), gen_#:1:true:false3_4(n143674_4)) → true, rt ∈ Ω(1 + n143674₄)
*'(gen_#:1:true:false3_4(n242826_4), gen_#:1:true:false3_4(0)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n242826₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

No more defined symbols left to analyse.

(46) LowerBoundsProof (EQUIVALENT transformation)

The lowerbound Ω(n¹) was proven with the following lemma:
-(gen_#:1:true:false3_4(n108770_4), gen_#:1:true:false3_4(n108770_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n108770₄)

(47) BOUNDS(n^1, INF)

(48) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
-(gen_#:1:true:false3_4(n108770_4), gen_#:1:true:false3_4(n108770_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n108770₄)
eq(gen_#:1:true:false3_4(n111029_4), gen_#:1:true:false3_4(n111029_4)) → true, rt ∈ Ω(1 + n111029₄)
ge(gen_#:1:true:false3_4(n143674_4), gen_#:1:true:false3_4(n143674_4)) → true, rt ∈ Ω(1 + n143674₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

No more defined symbols left to analyse.

(49) LowerBoundsProof (EQUIVALENT transformation)

The lowerbound Ω(n¹) was proven with the following lemma:
-(gen_#:1:true:false3_4(n108770_4), gen_#:1:true:false3_4(n108770_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n108770₄)

(50) BOUNDS(n^1, INF)

(51) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
-(gen_#:1:true:false3_4(n108770_4), gen_#:1:true:false3_4(n108770_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n108770₄)
eq(gen_#:1:true:false3_4(n111029_4), gen_#:1:true:false3_4(n111029_4)) → true, rt ∈ Ω(1 + n111029₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

No more defined symbols left to analyse.

(52) LowerBoundsProof (EQUIVALENT transformation)

The lowerbound Ω(n¹) was proven with the following lemma:
-(gen_#:1:true:false3_4(n108770_4), gen_#:1:true:false3_4(n108770_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n108770₄)

(53) BOUNDS(n^1, INF)

(54) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
-(gen_#:1:true:false3_4(n108770_4), gen_#:1:true:false3_4(n108770_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n108770₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

No more defined symbols left to analyse.

(55) LowerBoundsProof (EQUIVALENT transformation)

The lowerbound Ω(n¹) was proven with the following lemma:
-(gen_#:1:true:false3_4(n108770_4), gen_#:1:true:false3_4(n108770_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n108770₄)

(56) BOUNDS(n^1, INF)